#pragma once



template<class T>
bool isPrime(T n)
{
	if (n < 2)return false;
	for (T i = 2;i*i < n;++i)
		if (n%i == 0)
			return false;
	return true;
}

template<class T>
T gcd(T a, T b)
{
	if (b == 0) return a;
	else return gcd(b, a%b);
}

template<class T>
T exgcd(T a, T b, T &x, T &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	T ans = exgcd(b, a%b, x, y);
	T temp = x;
	x = y;
	y = temp - a / b*y;
	return ans;
}

template<class T>
T invmod(T a, T m)
{
	T x, y;
	T gcd = exgcd(a, m, x, y);
	if (gcd != 1) return -1;
	x /= gcd;
	if (m < 0) m = -m;
	T ans = x%m;
	if (ans <= 0) ans += m;
	return ans;
}

template<class T>
T powmod(T x, T e, T n)
{
	T ans = 1;
	if (e <= 0) ans = 1;
	else if (e == 1) ans = x%n;
	else if (e % 2 == 0)
	{
		T temp = powmod(x, e / 2, n);
		ans = (temp*temp) % n;
	}
	else
	{
		--e;
		T temp = powmod(x, e / 2, n);
		ans = (((temp*temp) % n)*x) % n;
	}
	return ans;
}